#define _CRT_SECURE_NO_WARNINGS 1

#include<iostream>
#include<vector>

using namespace std;

int coinChange(vector<int>& coins, int amount) {
    int n = coins.size(), INF = 0x3f3f3f3f;
    vector<int> f(amount + 1, INF);
    f[0] = 0;
    for (int i = 1; i <= n; i++)
        for (int j = coins[i - 1]; j <= amount; j++)
            f[j] = min(f[j], f[j - coins[i - 1]] + 1);
    return f[amount] == INF ? -1 : f[amount];
}

int numSquares(int n) {
    vector<int> nums;
    for (int i = 1; i < n; i++)
        if (i * i <= n)
            nums.push_back(i * i);

    vector<int> f(n + 1, 0x3f3f3f3f);
    f[0] = 0, f[1] = 1;
    for (auto x : nums)
        for (int j = x; j <= n; j++)
            f[j] = min(f[j], f[j - x] + 1);

    return f[n];
}